/* Copyright (C) 2014 chee <chee.think@gmail.com>
 * 常见算法习题练习
 */
#include <iostream>
#include <vector>

/* Ex-1:
 * 给定整数A1, A2, ..., An（可能有负数），求该序列中和最大的子序列。
 */

/* Ex-1-01
 */
auto max_subseq_sum(const std::vector<int>& vec) -> int {
    int max_sum {0};

    for (auto i = vec.cbegin(); i != vec.cend(); ++i) {
        for (auto j = i; j != vec.cend(); ++j) {
            int this_sum {0};

            for (auto k = i; k <= j; ++k) {
                this_sum += *k;
            } 
            
            if (this_sum > max_sum) {
                max_sum = this_sum;
            }
        }
    }

    return max_sum;
}

int main(int argc, const char* argv[]) {
    std::vector<int> arr { -2, 5, 9, 11, -27, 0, -2, 18 };
    auto sum = max_subseq_sum(arr);

    std::cout << "the sum is " << sum << std::endl;

    return 0;
}
